'''
    在排序数组中找元素的第一个元素和最后一个元素
    思路：
        利用二分查找找到元素的左边界
        再利用二分查找找到元素的右边界
'''

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        #找左边界
        def found_left(nums,target):
            left,right = 0,len(nums) -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid -1 
                elif nums[mid] == target:
                    right = mid - 1
            if left < 0 or left >= len(nums):
                return -1
            
            return left if nums[left] == target else -1
         #找右边界
        def found_right(nums,target):
            left,right = 0,len(nums) -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1 
                elif nums[mid] == target:
                    left = mid  + 1
            if right < 0 or right >= len(nums):
                return -1
            
            return right if nums[right] == target else -1
        
        left = found_left(nums,target)
        right = found_right(nums,target)
        return [left,right]